W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Stało się - Trójkątowie najechali Bajtocję! Bajtocja leży na wyspie i zajmuje całą jej powierzchnię. Wyspa ta ma kształt wielokąta wypukłego (tzn. takiego wielokąta, którego każdy kąt wewnętrzny jest mniejszy od ). W Bajtocji znajduje się pewna liczba fabryk oprogramowania. Każda fabryka przynosi pewne stałe zyski lub straty.
Trójkątowie postanowili opanować taki fragment Bajtocji, który:
Król Bajtocji, Bajtazar, zastanawia się, jak duże straty dla gospodarki kraju może przynieść najazd Trójkątów. Pomóż mu i napisz program, który wyznaczy sumę zysków i strat przynoszonych przez fabryki, które chcą opanować Trójkątowie.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę wierzchołków wielokąta-wyspy. Kolejnych wierszy wejścia zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające współrzędne i kolejnych wierzchołków wyspy, podane w kolejności zgodnej z kierunkiem ruchu wskazówek zegara. Wiersz -gi zawiera jedną liczbę całkowitą (), oznaczającą liczbę fabryk. Kolejne wierszy zawiera po trzy liczby całkowite , i (, ), oddzielone pojedynczymi odstępami i oznaczające odpowiednio: współrzędne i -tej fabryki, oraz zysk (dla ) bądź stratę (dla ), którą ta fabryka przynosi. Każda fabryka leży na wyspie-wielokącie, tzn. wewnątrz niej lub na jej brzegu. Kilka fabryk może leżeć w tym samym miejscu, tj. mieć te same współrzędne.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalną sumę zysków i strat przynoszonych przez fabryki znajdujące się w obrębie trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy. Może się zdarzyć, że liczba ta będzie ujemna.
Dla danych wejściowych:
5 4 1 1 4 8 9 11 5 8 1 4 7 2 3 6 3 -1 4 5 3 9 6 -4
poprawną odpowiedzią jest:
5
Autor zadania: Jakub Radoszewski.